package DecChallenges;

//link: https://leetcode.com/problems/find-words-that-can-be-formed-by-characters/?envType=daily-question&envId=2023-12-02
//归类:HashMap
public class Day2_P1160 {
    public static void main(String[] args) {
        Day2_P1160 q = new Day2_P1160();
        String[] words = {"cat","bt","hat","tree"};
        String chars = "atach";
        System.out.println(q.countCharacters(words, chars));
    }

    public int countCharacters2(String[] words, String chars) {
        int[] fmap = new int[26];
        //record the frequency of chars
        for(char c: chars.toCharArray()) {
            fmap[c - 'a']++;
        }

        int[] gathered = null; //used to roll back
        boolean flag = true; //whether one word can be formed
        int ans = 0;
        for(String word: words) {
            gathered = new int[26];
            for(char c: word.toCharArray()) {
                gathered[c - 'a']++;
                if(gathered[c - 'a'] > fmap[c - 'a']) {
                    flag = false;
                    break;
                }
            }
            if(flag) {
                ans += word.length();
            }
            flag = true;
        }
        return ans;
    }

    public int countCharacters(String[] words, String chars) {
        int[] fmap = new int[26];
        //record the frequency of chars
        for(char c: chars.toCharArray()) {
            fmap[c - 'a']++;
        }

        int[] gathered = null; //used to roll back if one word cannot be formed
        boolean flag = true; //whether one word can be formed
        int ans = 0;
        for(String word: words) {
            gathered = new int[26];
            for(char c: word.toCharArray()) {
                if(fmap[c - 'a'] == 0) {
                    //as long as one char cannot be found in fmap
                    //the whole word cannot be formed
                    flag = false;
                    break;
                }
                gathered[c - 'a']++;
                fmap[c - 'a']--;
            }
            if(flag) {
                ans += word.length();
            }
            //roll back
            recover(fmap, gathered);
            flag = true;
        }
        return ans;
    }

    public void recover(int[] fmap, int[] gathered) {
        for(int i = 0; i < 26; i++) {
            fmap[i] += gathered[i];
        }
    }
}
